1. Field of the Invention
This invention relates to cache memories and, more particularly, to parity error detection for cache memories.
2. Background Information
It is axiomatic that data entering a data processor, whether originating in a local memory, or received from a remote source via a communication link, must be correct. For this reason many error detecting codes (EDC) are frequently used to insure the integrity of the information to be processed. For example, a parity bit may be added to units of data being stored in computer memories to detect a single bit error in the data unit when the unit is read.
To speed memory access, computers often use cache memory, which is a small high speed memory that provides fast access to a copy of the data in current use. Various schemes for managing data transfers between the main memory and the cache memory are well known in the art. All cache memories must provide a means for finding data associated with an address in the larger main memory in the smaller cache memory. One commonly used technique for constructing a cache memory is the set associative cache.
A set associative cache memory contains a predetermined number of cache lines, each line containing a predetermined number of bytes. The low order address bits are used to locate a line and a byte in the cache memory corresponding to any data byte in the main memory. However, there are many bytes of data in the main memory that have the same low order address bits and which would be located in the same place in the cache memory. Therefore, the unused high order address bit, termed the tag bits, are stored in an associated tag memory. When cache memory is accessed, the tag bits stored on the line being accessed are compared to the high order incoming address bits to see if the cache memory contains the byte being accessed. If the tag bits are the same as the high order address bits then there is a cache hit, the cache contains a copy of the main memory address being accessed. Thus, a cache memory read involves first reading the tag memory to see if the cache line contain the desired data, and then reading the data from the data memory if there is a hit.
Cache memory, like all memory, is subject to data corruption. Error detection is especially desirable in cache memory because the majority of memory accesses are likely to involve the cache memory in a well-designed system. It is important to detect errors in the tag memory because such errors render the tag comparison meaningless and lead to the possibility of accessing the incorrect unit of data or failing to access the most current data stored in the cache.
N-way set associative cache memories provide N locations, where N is 2 or more, that are accessed by the same low order address bits. This allows the number of conflicts for use of a storage location to be reduced because each main memory location can be located in 1 of N locations. When an N-way cache memory is accessed, N tags are retrieved and each tag is compared to the high order incoming address bits by 1 of N comparators to determine if any of the N ways of the cache memory contains the byte being accessed. The output of the N comparators generates a way selection value that indicates which of the N ways contains the byte being accessed if there is a cache hit. The way selection value causes an N to 1 multiplexer to select the data from the matching 1 of N data memories.
An N-way tag memory with parity error detection will store a parity bit for each entry in each of the N tag memories. It is known in the prior art to provide the way selection value to an N to 1 multiplexer to select the tag data from the appropriate 1 of N tag memories for parity checking of the tag value that generated the hit indication. If a parity error is detected, then an error signal is sent to the processor to indicate that the data provided are unreliable. Such errors are often fatal because it is difficult for the processor to provide correction of errors detected at the time that the data have been requested.
Accordingly, there is a need for a method and apparatus that allows cache tag errors to be detected before a data request is being fulfilled to increase the likelihood of correcting the detected error.